/*
============================================================================
Name        : dd_btree.c
Author      : Jian (raphyer@hotmail.com)
Version     :
Copyright   : GPL
Description : dd_btree.c - source file
============================================================================
*/

/* INCLUDE FILES */
#include "dd_btree.h"
#include "dd_log.h"


/* MACROS */

#define BTREE_GRADE(t)              ((t)->M)
#define BTREE_MIN_NODE_CHILD(t)     _min_child_count(t)
#define BTREE_REASSIGN_RIGHT(t)     _min_child_count(t)
#define BTREE_REASSIGN_LEFT(t)      (BTREE_GRADE(t) + 1 - BTREE_REASSIGN_RIGHT(t))

#define __ptr_size(count)       ((count) * sizeof(void*))
#define _child(p, i)            (((p)->data.children)[(i)])
#define __update_key(n)         ((n)->key = (n)->data.children[(n)->childCount-1]->key)


static __dd_inline DD_BOOL _is_node(const dd_btree_node* node)
{
    __DD_ASSERT(node) ;
    return (node->childCount > 0) ;
}

static __dd_inline DD_BOOL _is_leaf(const dd_btree_node* node)
{
    __DD_ASSERT(node) ;
    return (node->childCount == 0) ;
}

static __dd_inline DD_BOOL _child_is_leaf(const dd_btree_node* node)
{
    __DD_ASSERT(node && node->childCount > 0) ;

    return (_is_leaf(_child(node, 0))) ;
}

static __dd_inline int _min_child_count(const dd_btree* btree)
{
    return (int)((btree->M / 2) + (btree->M % 2)) ;
}


static dd_btree_node* _init_leaf(dd_btree_key* key, dd_btree_value* value)
{
    dd_btree_node* leaf = (dd_btree_node*)dd_malloc(sizeof(dd_btree_node)) ;
    memset(leaf, 0,sizeof(dd_btree_node)) ;
    
    leaf->childCount	    = 0 ;
    leaf->data.leafValue   = value ;
    leaf->key               = key ;
    
    return leaf ;
}

static dd_btree_node* _init_node(const dd_btree* btree)
{
    dd_btree_node* node = (dd_btree_node*)dd_malloc(sizeof(dd_btree_node) + (BTREE_GRADE(btree) + 1) * sizeof(dd_btree_node*)) ;
    memset(node, 0, sizeof(dd_btree_node) + (BTREE_GRADE(btree) + 1) * sizeof(dd_btree_node*)) ;
    
    node->childCount   = 0 ;
    node->data.children = (dd_btree_node**)(((char*)node + sizeof(dd_btree_node))) ;
    
    return node ;
}


static void _deinit_node(dd_btree_node* node)
{
    int i = 0 ;
    
    __DD_ASSERT(node) ;
    
    for (; i < node->childCount; i++) {
        _deinit_node(_child(node, i)) ;
    }
    
    dd_destroy(node) ;
}

static dd_btree_node* _find_by_key(const dd_btree* btree, const dd_btree_key* key)
{	
    if (_is_leaf(btree->root)) {
        
        if (btree->root->key && btree->key_compare(btree->root->key, key) == 0)
            return btree->root;
        
        return NULL ;
    }
    
    if (btree->key_compare(key, btree->root->key) > 0)  /* the key is bigger than the biggest element in the tree */
        return NULL ;
    
    {
        int i  ;
        dd_btree_node* tmp_node = btree->root ; 
        
        FindByKey:
        for (i = 0 ; i < tmp_node->childCount; i++)
        {
            int cmp = btree->key_compare(key, tmp_node->data.children[i]->key) ;
            
            if (cmp < 0) {
                
                if (_is_node(tmp_node->data.children[i])) {
                    tmp_node = tmp_node->data.children[i] ;
                    goto FindByKey ;
                }
                else {
                    return NULL;
                }
            }
            
            if (cmp == 0) {
                
                if (_is_node(tmp_node->data.children[i])) {
                    tmp_node = tmp_node->data.children[i] ;
                    goto FindByKey ;
                }
                else {	/* leaf */
                    return tmp_node->data.children[i];
                }
            }
        }
    }
    
    return NULL ;
}


static int _find_pos(dd_btree* btree, dd_btree_node* parent, dd_btree_key* key)
{
    int i = 0 ;
    
    for (; i < parent->childCount; i++) {
        if (btree->key_compare(_child(parent, i)->key, key) >= 0) {
            return i ;
        }
    }
    
    __DD_ASSERT(btree->key_compare(key, btree->root->key) >= 0) ;
    
    return parent->childCount ;
}

static void _try_split(dd_btree* btree, dd_btree_node* node, int node_pos, dd_btree_node* parent)
{
    __DD_ASSERT(node && _is_node(node) && node->childCount <= BTREE_GRADE(btree) + 1) ;

    if (node->childCount == BTREE_GRADE(btree) + 1) {
        /* 
         * Node's child count is too big, need to split some of it's children to a new node 
         * policy: node get BTREE_REASSIGN_LEFT child and new node get BTREE_REASSIGN_RIGHT child 
         * and node is smaller than new_node
         */
        int new_pos             = node_pos + 1 ;
        dd_btree_node* new_node = _init_node(btree) ;
        memmove(new_node->data.children, &_child(node, BTREE_REASSIGN_LEFT(btree)), __ptr_size(BTREE_REASSIGN_RIGHT(btree))) ;
        new_node->childCount = BTREE_REASSIGN_RIGHT(btree) ;
        __update_key(new_node) ;
        
        node->childCount = BTREE_REASSIGN_LEFT(btree) ;
        __update_key(node) ;
        
        if (parent) {
            if (new_pos < parent->childCount)
                memmove( &_child(parent, new_pos + 1), &_child(parent, new_pos), __ptr_size(BTREE_GRADE(btree) - new_pos)) ;
            parent->data.children[new_pos] = new_node ;
            parent->childCount++ ;
            __update_key(parent) ;
        }
        else {
            /* new root */
            dd_btree_node* new_root		= _init_node(btree) ;
            new_root->childCount		= 2 ;
            new_root->data.children[0]	= btree->root ;
            new_root->data.children[1]	= new_node ;
            __update_key(new_root) ;

            __DD_ASSERT(node == btree->root) ;
            
            btree->root                 = new_root ;
        }
    }
}

static void _insert(dd_btree* btree, dd_btree_node* leaf, dd_btree_node* parent)
{
    int insert_pos = 0 ;

    __DD_ASSERT(btree && leaf && parent && parent->childCount <= BTREE_GRADE(btree)) ;

    insert_pos = _find_pos(btree, parent, leaf->key) ;

    if (_child_is_leaf(parent)) {

        if (insert_pos == parent->childCount) {
            /* The leaf must bigger than the key in the btree and the parent is the rightest node in the btree */
            __DD_ASSERT(btree->key_compare(leaf->key, btree->root->key) > 0) ;
            parent->key = leaf->key ; 
        }
        else { 
            memmove(&_child(parent, insert_pos+1), &_child(parent, insert_pos), __ptr_size(parent->childCount - insert_pos)) ;
        }

        _child(parent, insert_pos)  = leaf ;
        parent->childCount++ ;
        return ;
    }

    /* parent's children is node too */
    {
        int node_pos     = 0 ;
        dd_btree_node* node = NULL ;
      
        if (insert_pos == parent->childCount) {
            node_pos    = parent->childCount - 1 ;
            node        = _child(parent, parent->childCount-1) ;
        }
        else {
            node_pos    = insert_pos ;
            node        = _child(parent, insert_pos) ;
        }
        
        _insert(btree, leaf, node) ;

        /* Test if the node need to be split */ 
        parent->key = __update_key(parent) ;
        _try_split(btree, node, node_pos, parent) ;

    }
}


static void _rob_child(dd_btree_node* node, int pos, dd_btree_node* parent, DD_BOOL from_pre)
{
    __DD_ASSERT(node && parent) ;
    __DD_ASSERT(from_pre ? (pos > 0) : (pos < parent->childCount-1)) ;
    
    if (from_pre) {     /* pre_sib->max_child TO node->0 */
        
        dd_btree_node* pre_sib = parent->data.children[pos - 1] ;
        memmove(&(node->data.children[1]), &(node->data.children[0]), __ptr_size(node->childCount)) ;	
        node->data.children[0] = pre_sib->data.children[pre_sib->childCount - 1] ;
        node->childCount++ ;
        pre_sib->childCount-- ;
        __update_key(pre_sib) ;
        
    }
    else {  /* next_sib->0 TO node->max */
        dd_btree_node* next_sib = parent->data.children[pos + 1] ;
        node->data.children[node->childCount] = next_sib->data.children[0] ;
        node->childCount++ ;
        __update_key(node) ;
        memmove(&(next_sib->data.children[0]), &(next_sib->data.children[1]), __ptr_size(next_sib->childCount-1)) ;
        next_sib->childCount-- ;
    }
}


static void _merge_normal(dd_btree* btree, dd_btree_node* merge_node, int pos, dd_btree_node* parent)
{
    /* First we find the sibling that it's childCount bigger than BTREE_MIN_NODE_CHILD */
    int inc     = pos + 1 ;	
    int dec     = pos - 1 ;
    int factor  = 0 ;
    int end     = 0 ;
    while (DD_TRUE)
    {
        if (dec < 0 && inc >= parent->childCount) {  /* NOT FOUND */
            
            if (pos > 0) {
                
                /* Append merge_node's children to the previous sibling node */
                dd_btree_node* pre_sib = parent->data.children[pos - 1] ;
                memcpy(&(pre_sib->data.children[pre_sib->childCount]), merge_node->data.children, __ptr_size(merge_node->childCount)) ;
                pre_sib->childCount += merge_node->childCount ;
                __update_key(pre_sib) ;
            }
            else {  /* pos == 0 */
                
                /* Append merge_node's children to the next sibling node == 1 */
                dd_btree_node* next_sib = parent->data.children[pos + 1] ;
                memmove(&(next_sib->data.children[merge_node->childCount]), next_sib->data.children, __ptr_size(next_sib->childCount)) ;
                memcpy(next_sib->data.children, merge_node->data.children, __ptr_size(merge_node->childCount)) ;
                next_sib->childCount += merge_node->childCount ;
                /* __update_key(next_sib) ; */                 
            }
            
            memmove(&(parent->data.children[pos]), &(parent->data.children[pos+1]), __ptr_size(BTREE_GRADE(btree) - 1 - pos)) ;
            
            parent->childCount-- ;
            
            __update_key(parent) ;
            
            merge_node->childCount = 0 ;
            _deinit_node(merge_node) ;
            
            return ;
        }
        
        if (dec >= 0 && (parent->data.children[dec]->childCount > BTREE_MIN_NODE_CHILD(btree)))
        {
            end = dec ;
            factor = -1;
            goto Bingo ;    /* break is work too */
        }
        
        if (inc < parent->childCount && (parent->data.children[inc]->childCount > BTREE_MIN_NODE_CHILD(btree)))
        {
            end = inc ;
            factor = 1 ;
            goto Bingo ;
        }
        
        dec-- ;
        inc++ ;
        
    }   /* end while (DD_TRUE) */
    
    Bingo:
    __DD_ASSERT(factor == -1 || factor == 1) ;
        
    while(pos != end)
    {
        _rob_child(parent->data.children[pos], pos, parent, (factor == -1)) ;
        pos += factor ;
    }
}

static void _merge_root(dd_btree* btree) 
{
    dd_btree_node* root  = btree->root ;
    dd_btree_node* child = _child(root, 0) ;
    root->childCount    = child->childCount ;
    root->key            = child->key ;
    if (child->childCount == 0)
        root->data.leafValue = child->data.leafValue ;
    else
        memcpy(root->data.children, child->data.children, __ptr_size(child->childCount)) ;
    
    child->childCount = 0 ;
    _deinit_node(child) ;
}

static void _try_merge(dd_btree* btree, dd_btree_node* merge_node, int pos, dd_btree_node* parent)
{
    __DD_ASSERT(merge_node && _is_node(merge_node)) ;

    if (merge_node->childCount >= BTREE_MIN_NODE_CHILD(btree))
        return ;

    if (parent && merge_node->childCount < BTREE_MIN_NODE_CHILD(btree)) {
        _merge_normal(btree, merge_node, pos, parent) ;
        return ;
    }

    if (!parent && merge_node->childCount < 2) {
        __DD_ASSERT(merge_node == btree->root) ;
        __DD_ASSERT(merge_node->childCount == 1) ;
        _merge_root(btree) ;
        return ;
    }
}


static dd_btree_value* _remove(dd_btree* btree, dd_btree_key* key, dd_btree_node* parent)
{
    int del_pos      = 0 ;
    
    __DD_ASSERT(btree && parent) ;
    __DD_ASSERT(parent != btree->root || parent->childCount >= 2) ;
    __DD_ASSERT(parent == btree->root || parent->childCount >= BTREE_MIN_NODE_CHILD(btree)) ;

    del_pos = _find_pos(btree, parent, key) ;
    
    if (del_pos == parent->childCount)
        return NULL ;

    if (_child_is_leaf(parent)) {

        if (btree->key_compare(key, _child(parent, del_pos)->key) == 0){
            dd_btree_value* val = _child(parent, del_pos)->data.leafValue ;
            _deinit_node(_child(parent, del_pos)) ;
            memmove(&_child(parent, del_pos), &_child(parent, del_pos + 1), __ptr_size(parent->childCount - del_pos - 1)) ;
            parent->childCount-- ;
            __update_key(parent) ;
            return val ;
        }

        return NULL ;
    }

    /* parent's children is node too */
    {
        dd_btree_value* val = _remove(btree, key, _child(parent, del_pos)) ;
        if (val) {
            _try_merge(btree, _child(parent, del_pos), del_pos, parent) ;
            return val ;
        }
    }

    return NULL ;
}



dd_btree* dd_btree_create(
    int M,
    int (*key_compare)(const dd_btree_key*, const dd_btree_key*), 
    void (*key_conflict)(dd_btree_key* , dd_btree_value*, dd_btree_key*, dd_btree_value*) 
)
{
    dd_btree* btree = NULL ;
    
    __DD_ASSERT_DEFENSE((M >= 3) && key_compare && key_conflict, return NULL) ;
    
    btree = (dd_btree*)dd_malloc(sizeof(dd_btree)) ;
    __DD_CHECK_MEM(btree, sizeof(dd_btree), return NULL) ;
    
    btree->M            = M ;
    btree->root			= _init_node(btree) ;
    btree->key_compare	= key_compare ;
    btree->key_conflict	= key_conflict ;
    
    return btree ;
}


void dd_btree_destroy(dd_btree* btree)
{
    __DD_ASSERT(btree) ;
    
    _deinit_node(btree->root) ;
    
    dd_destroy(btree) ;
}


dd_btree_value* dd_btree_find(const dd_btree* btree, dd_btree_key* key)
{
    __DD_ASSERT(btree && key) ;
    
    if (btree && key) {
        
        dd_btree_node* find_leaf = _find_by_key(btree, key) ;
        if (find_leaf)
            return find_leaf->data.leafValue ;
    }
    
    return NULL ;
}


void dd_btree_insert(dd_btree* btree, dd_btree_key* key, dd_btree_value* value)
{
    __DD_ASSERT(btree && key) ;

    
    if (btree && key) {
        
        dd_btree_node* root = btree->root ;

        __DD_ASSERT(root->childCount != 1) ;
        
        if (root->childCount >= 2 ) {
            _insert(btree, _init_leaf(key, value), root) ;
            __update_key(root) ;
            _try_split(btree, root, 0, NULL) ;
        }
        else if (root->key == NULL) {    /* Special for root: root may be empty at first */
            root->key				= key ;
            root->data.leafValue   = value ;
        }
        else /* if (root->key != NULL) */ {  /* Special for root: root may be a leaf */
            
            int cmp = btree->key_compare(root->key, key) ;
            
            if (cmp < 0) {
                
                dd_btree_value* save_value	= root->data.leafValue ;
                root->childCount			= 2 ;
                root->data.children			= (dd_btree_node**)(((char*)root + sizeof(dd_btree_node))) ;
                root->data.children[0]		= _init_leaf(root->key, save_value) ; 
                root->data.children[1]		= _init_leaf(key, value) ;
                root->key					= key ;
            }
            
            if (cmp > 0) {
                
                dd_btree_value* save_value	= root->data.leafValue ;
                root->childCount			= 2 ;
                root->data.children			= (dd_btree_node**)(((char*)root + sizeof(dd_btree_node))) ;
                root->data.children[0]		= _init_leaf(key, value) ; 
                root->data.children[1]		= _init_leaf(root->key, save_value) ;
                /* root key no change */
            }
            
            if (cmp == 0) {
                btree->key_conflict(root->key, root->data.leafValue, key, value) ;
            }
        }
    }
}


dd_btree_value* dd_btree_remove(dd_btree* btree, dd_btree_key* key)
{
    __DD_ASSERT(btree && key) ;	
    
    if (btree && key) {

        dd_btree_node* root = btree->root ;
        
        __DD_ASSERT(root->childCount != 1) ;

        if (root->childCount >= 2) {
            dd_btree_value* val = _remove(btree, key, root) ;
            if (val)
                _try_merge(btree, root, 0, NULL) ;
            return val ;
        }

        if (root->key && btree->key_compare(root->key, key) == 0) {
            root->key = NULL ;
            return root->data.leafValue;
        }
        return NULL ;
    }
    
    return NULL ;
}


#ifdef __DD_TEST

#include "dd_vector.h"

static int _tree_depth   = 0;
static int _usedNode     = 0 ;
static int _allocNode    = 0 ;
static int _leafNode     = 0 ;

static int _test_key_compare(const dd_btree_key* key1, const dd_btree_key* key2) 
{
    if (key1 < key2) return -1 ;
    
    if (key1 > key2) return 1 ;
    
    return 0 ;
}

static void _test_key_conflict(
    dd_btree_key* key_found_conflict, 
    dd_btree_value* value_found_conflict, 
    dd_btree_key* key_handle, 
    dd_btree_value* value_handle
) 
{
    __DD_ASSERT((int)key_found_conflict == (int)value_found_conflict && (int)key_handle == (int)value_handle 
        && (int)key_found_conflict == (int)key_handle) ;
}


static void _ut_print_node(const dd_btree_node* node)
{
    if ( _is_leaf(node) ) {
        __DD_ASSERT(node->childCount == 0) ;
        dd_log_error("LEAF key = %d, value = %d \n", (int)node->key, (int)node->data.leafValue) ;
        return ;
    }
    else {
        
        int i = 0 ; 
        dd_log_error("--- NODE key = %d, childCount = %d ---\n", (int)node->key, (int)node->childCount) ;
        for ( ; i < node->childCount; i++) {
            _ut_print_node(node->data.children[i]) ;
        }
    }
}


static int _ut_get_node_depth(const dd_btree* btree, const dd_btree_node* node)
{
    int depth = 0;
    const dd_btree_node* tmp_node = btree->root ;
    int i = 0;

    cmpDepth :
    i = 0 ;
    for ( ; i < tmp_node->childCount; i++ ) {
        if (btree->key_compare(tmp_node->data.children[i]->key, node->key) >= 0) {
            
            depth ++ ;

            if (_is_leaf(tmp_node->data.children[i]))
                return depth ;

            tmp_node = tmp_node->data.children[i] ;
            goto cmpDepth ;
        }
    }

    dd_log_error("_ut_get_node_depth error\n") ;
    _ut_print_node(node) ;
    return -1 ;
}


static DD_BOOL _ut_check_node(const dd_btree* btree, const dd_btree_node* node)
{
    if (_is_leaf(node)) {
        
        if (node->key != node->data.leafValue) {
            dd_log_error("_ut_check_node LEAF Check leafValue error\n") ;
            _ut_print_node(node) ;
            return DD_FALSE ;
        }
        
        if (node->childCount != 0) {
            dd_log_error("_ut_check_node LEAF Check childCount error\n") ;
            _ut_print_node(node) ;
            return DD_FALSE ;
        }
        
        if (_tree_depth == 0)
            _tree_depth = _ut_get_node_depth(btree, node) ;
        
        
        if (_tree_depth == -1 || _tree_depth != _ut_get_node_depth(btree, node)) {	/* All leaf must have the same depth */
            dd_log_error("_ut_check_node LEAF Check node depth = %d error\n", _tree_depth) ;
            _ut_print_node(node) ;
            return DD_FALSE ;
        }
        
    }
    else {
        
        int i = 0 ;
        
        if (node->childCount < BTREE_MIN_NODE_CHILD(btree)) {
            dd_log_error("_ut_check_node NODE Check childCount error") ;
            _ut_print_node(node) ;
            return DD_FALSE ;
        } 

        _usedNode += node->childCount ;
        _allocNode += 4 ;

        if (_child_is_leaf(node))
            _leafNode += node->childCount ;

        for(; i < node->childCount; i++){
            _ut_check_node(btree, node->data.children[i]) ;
            if (btree->key_compare(node->key, node->data.children[i]->key) < 0)
            {
                dd_log_error("_ut_check_node NODE Check key compare error") ;
                _ut_print_node(node) ;
                return DD_FALSE ;
            }
        }
    }
    
    return DD_TRUE ;
}


static DD_BOOL _ut_check_btree(const dd_btree* btree)
{
    dd_log_error("_ut_check_btree Start to check the node of tree\n") ;

    _tree_depth = 0 ;
    _usedNode = 0 ;
    _allocNode = 0 ;
    _leafNode = 0 ;
    
    if(btree->root->childCount >= 2 &&  !_ut_check_node(btree, btree->root)) {
        dd_log_error("_ut_check_btree  _ut_check_node Check node FAILED\n") ;
        return DD_FALSE ;
    }
    
    dd_log_error("_ut_check_btree check tree SUCCEED and DEPTH = %d and Alloc = %d, Use = %d Leaf = %d, Useage = %d%%, , leafUsage = %d%%\n",
        _tree_depth, _allocNode, _usedNode, _leafNode, 
        _allocNode > 0 ? (_usedNode * 100 /_allocNode) : 0, _allocNode > 0 ? (_leafNode * 100 /_allocNode) : 0) ;
    
    return DD_TRUE ;
}


#define __TEST_TIMES            (10000 + 1)
#define __TEST_BTREE_GRADE      4
#define __TEST_BY_RANDOM 


DD_BOOL dd_btree_test()
{
    dd_btree* test_btree	= dd_btree_create(__TEST_BTREE_GRADE, _test_key_compare, _test_key_conflict) ;
    dd_vector* vec			= dd_vector_create(__TEST_TIMES) ;
    int i					= 0 ;

    
#ifdef __TEST_BY_RANDOM
    srand((DD_UINT)time(0)) ;
    i = 1;
    for (; i< __TEST_TIMES; i++) {
        int k = (rand() * i) ;
        if (k != 0 && (int)dd_btree_find(test_btree, (dd_btree_key*)k) != k )  {
            dd_btree_insert(test_btree, (dd_btree_key*)k, (dd_btree_value*)k) ;
            dd_vector_append(vec, (void*)k) ;

            if (__TEST_TIMES < 30) {
                dd_log_error("=============== After insert %d ===============\n", i) ;
                _ut_print_node(test_btree->root) ;
            }
        }
    }
#else
    i = 1;
    for (; i < __TEST_TIMES; i++) {
        int k = i;
        dd_btree_insert(test_btree, (dd_btree_key*)k, (dd_btree_value*)k) ;
        dd_vector_append(vec, (void*)k) ;
        
        if (__TEST_TIMES < 30) {
            dd_log_error("=============== After insert %d ===============\n", i) ;
            _ut_print_node(test_btree->root) ;
        }
    }
     
#endif
    _ut_check_btree(test_btree) ;
    
    i = 0 ;
    for ( ;i < dd_vector_count(vec); i++ ) {
        int find_value = (int)dd_btree_find(test_btree, (dd_btree_key*)dd_vector_get(vec, i)) ;
        if (!find_value || find_value != (int)dd_vector_get(vec, i)) {
            dd_log_error("dd_btree_find error 1111\n") ;
            return DD_FALSE ;
        }
    }
    
    dd_log_error("Add %d leaf to btree\n", dd_vector_count(vec)) ;
   
    i = 1 ;
    for ( ;i < dd_vector_count(vec); i++ ) {
        
        if ( i % 2 == 0 ) {
            int del_value = (int)dd_btree_remove(test_btree, (dd_btree_key*)dd_vector_get(vec, i)) ; ;
            
            if (!del_value || del_value != (int)dd_vector_get(vec, i)) {
                dd_log_error("dd_btree_remove error 1111 \n") ;
                return DD_FALSE ;
            }
            dd_vector_delete_by_index(vec, i) ;

            if (__TEST_TIMES < 30) {
                dd_log_error("=============== After Remove %d ===============\n", i) ;
                _ut_print_node(test_btree->root) ;
            }
        }
    }
    
    dd_log_error("After doing  random Remove Leave %d leaf in btree\n", dd_vector_count(vec)) ;
    
    _ut_check_btree(test_btree) ;
    
    i = 0 ;
    for ( ;i < dd_vector_count(vec); i++ ) {
        int find_value = (int)dd_btree_find(test_btree, (dd_btree_key*)dd_vector_get(vec, i)) ;
        if (!find_value || find_value != (int)dd_vector_get(vec, i)) {
            dd_log_error("dd_btree_find  error 22222\n") ;
            return DD_FALSE ;
        }
    }

    while(dd_vector_count(vec) > 0) {

        int del_value = (int)dd_btree_remove(test_btree, (dd_btree_key*)dd_vector_get(vec, 0)) ; ;
        
        if (!del_value || del_value != (int)dd_vector_get(vec, 0)) {
            dd_log_error("dd_btree_remove error 22222 \n") ;
            return DD_FALSE ;
        }
        dd_vector_delete_by_index(vec, 0) ;
    }

    dd_log_error("After doing  Remove all Leave %d leaf in btree\n", dd_vector_count(vec)) ;

     _ut_check_btree(test_btree) ;

    if (test_btree->root->key != NULL || test_btree->root->childCount != 0)
    {
        dd_log_error("Test empty tree error \n") ;
        return DD_FALSE ;
    }   
    
    dd_btree_destroy(test_btree) ;
    
    dd_vector_destroy(vec, NULL) ;
    
    return DD_TRUE ;
}

#endif	/* __DD_TEST */


/* End of File */
